package com.mango.leet.code.week1.game288;

/**
 * 6037. 按奇偶性交换后的最大数字
 */
/**
 * 给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。
 *
 * 返回交换 任意 次之后 num 的 最大 可能值。
 *
 *
 *
 * 示例 1：
 *
 * 输入：num = 1234
 * 输出：3412
 * 解释：交换数字 3 和数字 1 ，结果得到 3214 。
 * 交换数字 2 和数字 4 ，结果得到 3412 。
 * 注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。
 * 注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。
 * 示例 2：
 *
 * 输入：num = 65875
 * 输出：87655
 * 解释：交换数字 8 和数字 6 ，结果得到 85675 。
 * 交换数字 5 和数字 7 ，结果得到 87655 。
 * 注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。
 *
 *
 * 提示：
 *
 * 1 <= num <= 109
 */

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author: mango
 * @Date: 2022/4/10 10:33 上午
 */
public class LC6037 {
    public static void main(String[] args) {
        System.out.println(new Solution().largestInteger(65875));
    }
    static class Solution {
        public int largestInteger(int num) {
            String numStr = num + "";
            PriorityQueue<Integer> pq0 = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
            PriorityQueue<Integer> pq1 = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
            Map<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<numStr.length();i++){
                Integer value = Integer.valueOf(String.valueOf(numStr.charAt(i)));
                if(value % 2 == 1){
                    pq1.add(value);
                }else{
                    pq0.add(value);
                }
                map.put(i,value % 2);
            }
            String resultStr = "";
            for(int i=0;i<numStr.length();i++){
                int index = map.get(i);
                resultStr += index == 0 ? pq0.poll() : pq1.poll();
            }
            return Integer.valueOf(resultStr);
        }
    }
}
